#include"Sort.h"


void Print(int* nums,int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d", nums[i]);
    }
}

int GetMidNum(int* nums, int left, int right)
{
    int mid = (left + right) / 2;
    if (nums[left] < nums[mid])
    {
        if (nums[mid] < nums[right])
        {
            return mid;
        }
        else if (nums[left] < nums[right])
        {
            return right;
        }
        else {
            return left;
        }
    }
    else {
        if (nums[left] < nums[right])
        {
            return left;
        }
        else if (nums[mid] > nums[right])
        {
            return mid;
        }
        else
        {
            return right;
        }
    }
}
void Swap(int* p1, int* p2)
{
    int x = *p1;
    *p1 = *p2;
    *p2 = x;
}
void QuickSort(int* nums, int left, int right)
{
    if (left >= right)
        return;
    // int midi=GetMidNum(nums,left,right);
    //if(midi !=left)
    //{
      //  Swap(&nums[left],&nums[midi]);
    //}
    int randi = left + rand() % (right - left);
    Swap(&nums[randi], &nums[left]);
    int keyi = left;
    int begin = left, end = right;
    while (left < right)
    {
        while (left<right &&nums[right] >= nums[keyi])
            right--;
        while (left<right &&nums[left] <= nums[keyi])
            left++;

        Swap(&nums[left], &nums[right]);
    }
    Swap(&nums[left], &nums[keyi]);
    keyi = left;
    //[begin,keyi-1]keyi[keyi+1,end];
    QuickSort(nums, begin, keyi - 1);
    QuickSort(nums, keyi + 1, end);

}
